1. Field of the Invention
The invention relates generally to the field of processor chips and specifically to the field of Single-Instruction Multiple-Data (SIMD) processors. More particularly, the present invention relates to Linear Feedback Shift Register (LFSR) implementation in a SIMD processing system.
2. Background
Linear Feedback Shift Registers (LFSRs) are commonly used in applications where pseudo-random bit streams are required. LFSRs are the functional building blocks of circuits like the pseudo-random noise (PN) code generator and Gold code generators commonly used in Code Division Multiple Access (CDMA) systems. These random numbers are used a wide variety of applications, including data encryption, circuit testing, system simulation and Monte Carlo method. In the past, random number generation is done either in software on a scalar processor, or in hardware using shift-registers and exclusive-or gates. These generate one bit of output at a time. The data generation rate of these approaches is nowhere near adequate of what is needed by the latest generation of systems. SIMD and other processors like to consume large amounts of data in parallel because of their inherent parallelism. Several hardware approaches have been used to generate LFSR output at a much higher data rate. Accumulation method is a straightforward extension of previous one-bit methods. In this method, we can obtain an N-bit value by accumulating the one-bit N times. This can be done either by utilizing N copies of the identical hardware or by repeating the one-bit generator for N clocks. Leap-Forward LFSR technique advances the LFSR N steps in one clock cycle. This is based on the observation that LFSR is a linear system and can be written in vector format. Lagged Fibonacci method processes an N-bit word directly using exclusive-OR operator, which can be bit wise XOR, addition, or multiplication. This approach requires L previous values to be memorized, i.e., kept in FIFO register file memory.
All these hardware approaches require considerable number of gates to implement this as a fixed-function. This means these gates cannot be used for other functions, or even for a different type of random number. Applications nowadays may require several different type of LFSRs and each of these has to be implemented separately.
Multiple-Bit Leap-Forward LFSR
Leap-forward LFSR method utilizes only one LFSR and shifts out several bits. This method is based on the observation that an LFSR is a linear system and the register state can be written in vector format:Q(i+1)=A·q(i)
In this equation, q(i+1) and q(i) are the contents of shift register at (i+1)th and ith steps, and A is the transition matrix. After the LFSR advances k steps, the equation becomes
                                             Q            ⁡                          (                              i                +                k                            )                                =                    ⁢                      A            ·                          q              ⁡                              (                                  i                  +                  k                  -                  1                                )                                                                                  =                    ⁢                      A            ·                          (                              A                ·                                  q                  ⁡                                      (                                          i                      +                      k                      -                      2                                        )                                                                                                                    =                    ⁢                                    A              2                        ·                          q              ⁡                              (                                  i                  +                  k                  -                  2                                )                                                                                  =                    ⁢          …                                                          Q            ⁡                          (                              i                +                k                            )                                =                    ⁢                                    A              k                        ·                          q              ⁡                              (                i                )                                                        
The matrix calculation is such that logical AND operation is used instead of the traditional multiply and exclusive-OR operation is used instead of the traditional summation in matrix multiplication. The symbol “·” represents the multiply which is implemented as binary AND operation. Thus, we can calculate Ak from A. Such an LFSR could leap k steps in one clock cycle.
Let us use the 4-bit LFSR as an example of how matrix operations are carried out. FIG. 1 illustrates the matrix operations.